package mySqrt;

public class Solution {
    public int mySqrt(int x) {
        //       int res = 1;
        // 暴力
//        while(true){
//            if((long)res*res>=x){
//                return res-1;
//            }
//            res++;
//        }
        // 二分
        int l = 1;
        int r = x;
        int res = 0;
        while(l<=r){
            int mid = l+(r-l)>>1;
            // mid*mid<x ---> mid <x/mid
            if(mid<=x/mid){
                res = mid;
                l = mid +1;
            }else{
                r = mid-1;
            }
        }
        return res;
    }
    // 4 == 2
    // 9 == 3
    // 256 == 16

}
